#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/22 11:51
# @USER    : Shengji He
# @File    : MinimumPathSum.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        """
        Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which
        minimizes the sum of all numbers along its path.

        Note: You can only move either down or right at any point in time.

        Example:
            Input:

            [
              [1,3,1],

              [1,5,1],

              [4,2,1]
            ]

            Output: 7

            Explanation: Because the path 1→3→1→1→1 minimizes the sum.

        :param grid:
        :return:
        """
        m, n = len(grid), len(grid[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    dp[i][j] = grid[i][j]
                elif i == 0:
                    dp[i][j] = grid[i][j] + dp[i][j - 1]
                elif j == 0:
                    dp[i][j] = grid[i][j] + dp[i - 1][j]
                else:
                    dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])

        return dp[-1][-1]


if __name__ == '__main__':
    S = Solution()
    grid = \
        [
            [1, 3, 1],
            [1, 5, 1],
            [4, 2, 1]
        ]
    print(S.minPathSum(grid))
    print('done')
